1. Field of the Invention
The present invention relates generally to prime number generation, and more specifically to a system and method for efficiently searching for and generating prime numbers suitable for use in cryptographic systems.
2. Description of the Prior Art
Many different types of cryptographic security systems require a means for determining large prime numbers. As an example, public key cryptographic schemes require large prime numbers to produce cryptographic keys which are used to encipher and decipher data for the purposes of guaranteeing the confidentiality, reliability, and authenticity of information to be stored or transferred from one place to another. As an example, a bank requires some means for keeping financial transactions confidential, and for guaranteeing the authenticity of a financial transaction to prevent the wrongful transfer of money.
In a typical cryptographic scheme, an encryption process is performed to transform a plaintext message M into ciphertext C, and a decryption process is performed to transform the ciphertext C back into plaintext. In a public key cryptographic scheme, encryption and decryption processes are performed using a pair of cryptographic keys. In the most common application, a public key E defined as the pair {e, n} is used to encrypt the message, and a private key D defined as the pair {d, n} is typically used to decrypt the ciphertext. It is important to note that the public key, which may be publicly known, cannot be used to decrypt the ciphertext. Only the private key D, which is kept secret, can be used for decryption of a message encrypted by the public key E. As an example, consider that a sender needs to send an encrypted message M to a recipient. The recipient publishes his or her public key, making it known at least to the sender, and keeps his or her private key secret. The sender then uses the public key to encrypt a message, and send the encrypted message to the recipient who then uses the private key to decrypt the message. Any third party interpreting the encrypted message is unable to decrypt the message without knowing the private key. As further explained below, although the public key is related to the private key, it is computationally difficult to determine the private key from the public key.
One example of a public key cryptography system is the classic “RSA” scheme which capitalizes on the relative ease of generating a composite number as the product of two large prime numbers, as compared with the difficulty of factoring that composite number into its constituent primes. Another example of a public key cryptography system is the Multiprime extension of the RSA system which is described in U.S. patent application Ser. No. 09/328,726, filed on Oct. 26, 1998, by Collins et al. The RSA scheme uses a public key E including a composite number n and a number e, where n is defined by relationship (1), belown=p·q  (1)
where the factors p and q are different prime numbers, and e is a number relatively prime to (p−1) and (q−1). Importantly, the sender has access to the public key E (including n and e), but not to the prime factors p and q, which are kept secret by the owner.
The sender enciphers a message M (M<n) to create ciphertext C by computing the exponential relationship (3), below.C≡Me(mod n)  (3)
wherein the number e provides an exponent, and the composite number n provides a modulus. The recipient of the ciphertext C may decrypt the message M using the private key D, which includes a number d and the modulus n, in accordance with relationship (4), below.M≡Cd(mod n)  (4)
The number d, which provides a decryption exponent, is a multiplicative inverse ofe(mod(1 cm((p−1), (q−1))))  (5)so thate·d≡1(mod(1 cm((p−1), (q−1))))  (6)
where 1 cm((p−1), (q−1)) is the least common multiple of the numbers (p−1) and (q−1).
Most commercial implementations of the RSA cryptography scheme employ a different although equivalent relationship (7), below, for determining the decryption exponent d.d≡e−1 mod((p−1)(q−1))  (7)
The security of this public key cryptographic system relies on the fact that the prime factors p and q of the composite number n are required to compute the private key d, and it is computationally difficult to factor the composite number n into its prime factors p and q.
Cryptanalysis refers to techniques for deciphering encrypted data without prior knowledge of the keys being used. From the time a security scheme becomes publicly known and used, it is subjected to unrelenting attempts to break it. Security levels for encryption schemes are continually being raised in order to combat increasingly more intelligent cryptanalytic attacks.
Cryptanalysts are often more interested in discovering the keys used to decrypt data than in merely discovering the contents of a single message. The most basic method of finding a decryption key is to try all possibilities by an exhaustive key search until the correct key is found. A more sophisticated method is to attempt to factor the modulus n. One method for increasing the security level provided by a public key cryptography system is to increase the length Ln (i.e., size in bits) of the modulus n so that its prime factors p and q cannot be discovered by an exhaustive search or by practical factoring methods. As an example, very large modulus numbers having a long length Ln (e.g., on the order of 512 bits, 768 bits, 1024 bits, and 2048 bits) are now being used in cryptographic keys. In the classic 2-prime RSA encryption algorithm, each of the prime factors p and q has a length Lp which is equal to half the bit length of the modulus n. For example, if the modulus has a length of 1024 bits, then each of the prime factors would have a length Lp of 512 bits. Using cryptographic keys of this size requires a significant amount of computer resources to perform the encryption and decryption operations, but also require much greater resources of a potential attacker to discover the decryption key.
One tradeoff resulting from use of such large cryptographic key values is that the amount of computer processing power required to create a new cryptographic key pair increases as the lengths of the cryptographic key values increases.
In particular, an increasingly important performance issue is the time and processing power required for prime number generation. For purposes of the present invention, prime number generation refers to processing steps involved in searching for and verifying large prime numbers for use in cryptographic keys. Testing the primality of large candidate numbers is very processing intensive. Efficient prime number generation is becoming more important due to several technical developments besides the demand for increased cryptographic key lengths. First, encryption and decryption processes are now being employed for use with devices, such as cell phones and personal digital assistants (PDA's)), that do not provide a large amount of processing power. Therefore, it would be desirable to reduce the processing time required for large prime number generation so that the processing resources of even a cell phone or PDA could accomplish the task. Second, there is an ever increasing demand for more cryptographic keys. Smart cards are now being provided with unique public keys.
The most common technique for finding prime numbers is a search method which generally includes the steps of: generating a random odd number n0 in a predefined interval (e.g., the interval between 2L−1 and 2L); testing if the randomly generated number n0 is a prime number; and if n0 is not a prime number, selecting another candidate n1 in the predefined interval and determining if it is a prime number; and repeating these steps until a prime number is found. A large amount of time and processing power is required to find prime number because the relative frequency of occurrence of prime numbers decreases with size. The relative frequency of a randomly generated number being prime depends on the size of the number. As an example, for a random number n0 generated in the interval between 2L−1 and 2L, the probability that n0 is prime is roughly equal to 1/L or more approximately 1/(L.1n2). Therefore, the probability that a generated number having a length L is a prime number is inversely proportional to the length of the number. This presents an important problem in public key type cryptography systems where the level of security is dependent at least in part on the length L of the cryptographic keys because increasing the length L to enhance the level of security results in a decrease in the performance of the prime number generation system.
Primality testing, that is the sub-process of determining if a randomly generated number no is a prime number, is the most processing intensive aspect of prime number generation. Primality testing may be accomplished using any one of a wide variety of different techniques, or using a combination of different techniques. Probabilistic primality tests provide methods by which arbitrary positive integers are tested to provide partial information regarding their primality. As further explained below, conventional probabilistic primality testing typically utilizes a plurality of sequentially executed primality tests, each being performed including an exponentiation with respect to an associated base integer αi where 1≦i≦t. Any single execution of a probabilistic primality test on a number results in a declaration of the number as being either a possible prime or a definite composite. A result of execution of a primality test which declares the number to be composite establishes this with certainty, while a result which declares the number to be a possible prime does not establish primality with certainty. However, execution of a plurality of t of successive independent primality tests, each indicating that the integer is may be prime, provides for a cumulative probability of error that decreases as the number t increases. If the test is run t times independently on a composite number n, the probability that n is declared possible prime all t times (i.e., the probability of error) is at most (½)t, and may be much smaller.
Commonly used probabilistic primality tests include the Fermat primality test and the Miller-Rabin primality test. Fermat's theorem asserts that if n is a prime, and αi is any integer, 1≦αi≦n−1, then relationship (8), below, is true.αin−1≡1(mod n)  (8)
If congruency is not found in accordance with relationship (8), that is if the statement defined by relationship (8) is not true, then ∝i is said to be a “Fermat witness” to compositeness for n. If n is a composite number, and congruency is found in accordance with relationship (8), then n is said to be a pseudoprime to the base ∝i, and the integer ∝i is called a “Fermat liar” or a non-witness to the compositeness of n.
Computer readable instructions for implementing each iteration of relationship (8) may be executed by a processor to determine the veracity of relationship (8) which yields a result declaring either probable primality or compositeness. As mentioned above, for probabilistic primality tests such as the Fermat test, if the results of relationship (8) declare “prime”, then there is not sufficient evidence that the number n is indeed prime. Therefore, exponentiation tests in accordance with relationship (8) are typically repeated t times for α1, α2, . . . αt at to determine if each of the t tests declares “prime” in order to achieve an acceptable level of certainty that the candidate is a prime. It is still true that if the prime number candidate passes all of the congruency tests for α1, α2, . . . αt, then there is no guarantee that the candidate is a prime.
Because relationship (8) defines an exponentiation, a significant amount of time and processing resources are required to execute instructions for implementing relationship (8). In order to accelerate the prime number generation process, conventional prime number generation systems typically provide a processor and a single exponentiation unit communicatively coupled with the processor in order to reduce the burden on the processor and speed up the prime number generation process as further explained below. The exponentiation unit is typically an arithmetic logic unit (ALU).
In accordance with conventional prime number generation methods, the generalized steps of randomly generating an odd number n0 and determining if the number n0 is a prime are executed sequentially using the arithmetic unit. If the number n0 is determined to be composite, a next prime number n1 in a sequence of prime number candidates is generated by adding two to the previous number n0, and it is then determined if the number n1 is a prime. Furthermore, in accordance with conventional prime number generation methods, the t exponentiation tests in accordance with relationship (8) for α1, α2, . . . αt are typically executed in a sequential manner using the arithmetic unit to determine if each of the t tests declares “prime”.
Cryptographic key generation in accordance with conventional methods is very time consuming and processing intensive even with the use of a fast arithmetic unit. Approximately 20 to 30 seconds are required to generate a cryptographic key value in a device such as a cell phone or PDA using conventional methods. This is partially due to the fact that the prime numbers in a predefined interval (e.g., the interval between 2L−1 and 2L) are far apart, and it is therefore necessary to perform tests on approximately L candidates that are determined to be composite before finding a prime number.
What is needed is a system and method that enables fast and efficient probabilistic primality testing, and reduced computational effort for calculating exponentiations thereby providing fast and efficient generation of large random prime numbers.